package leetcode.p879;

/**
 * 动态规划
 *
 * @author: trtan
 * @date: 2021-06-09 08:48
 **/
public class ProfitableSchemes {
    /**
     * dp[i][j][k]代表前i个任务选择了j个员工利润至少为k的方案数
     * 其中j的数量要和i绑定，初始只能dp[0][0][0] = 1, 而不能有dp[0][i > 1][0] = 1，因为无任务时没有选择任何员工
     * @param n 员工数量
     * @param minProfit 最小利润
     * @param group 第i种工作需要group[i]个人
     * @param profit 完成第i种工作的利润为profit[i]
     * @return int
     * @author trtan
     * @date 2021/6/9 8:51
     */
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        final int MOD = 1000_000_000 + 7;
        int[][][] dp = new int[group.length + 1][n + 1][minProfit + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= minProfit; j++) {
                if (i == 0 && j == 0) {
                    dp[0][i][j] = 1;
                } else {
                    dp[0][i][j] = 0;
                }
            }
        }
        for(int i = 1; i <= group.length; i++) {
            int g = group[i - 1];
            int p = profit[i - 1];
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= minProfit; k++) {
                    if (g > j) {
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
                        dp[i][j][k] = (dp[i-1][j][k] + dp[i - 1][j - g][Math.max(0, k - p)]) % MOD;
                    }
                }
            }
        }
        int result = 0;
        for (int i = 0; i <= n; i++) {
            result = (result + dp[group.length][i][minProfit]) % MOD;
        }
        return result;
    }


    public int profitableSchemesTwo(int n, int minProfit, int[] group, int[] profit) {
        final int MOD = (int) 1e9 + 7;
        // i个员工利润为j的方案数
        int[][] dp = new int[n + 1][minProfit + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (int i = 0; i < group.length; i++) {
            for (int j = n; j >= group[i]; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    dp[j][k] = (dp[j][k] + dp[j - group[i]][Math.max(0, k - profit[i])]) % MOD;
                }
            }
        }
        return dp[n][minProfit];
    }
}
